package com.origin.niuke.array;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/2 21:28
 * 数组中的逆序对
 * 算法：归并排序
 */
public class NC118 {

    int res, mod = (int) (1e9 + 7);
    int[] tmpArr, array;
    public int InversePairs(int [] _array) {
        res = 0;
        array = _array;
        tmpArr = new int[array.length];
        divide(0, array.length - 1);
        return res;
    }

    private void divide(int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        divide(l, mid);
        divide(mid + 1, r);
        merge(mid, l, r);
    }

    private void merge(int mid, int l, int r) {
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (array[i] > array[j]) {
                tmpArr[k++] = array[j++];
                res += (mid - i + 1);
                res %= mod;
            } else tmpArr[k++] = array[i++];
        }
        while (i <= mid) tmpArr[k++] = array[i++];
        while (j <= r) tmpArr[k++] = array[j++];
        for (k = 0, i = l; i <= r; k++, i++) array[i] = tmpArr[k];
    }

}
